package com.duoduo.深度广度优先;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @program: algorithm
 * @description: 542. 01 矩阵
 * 给定一个由 0 和 1 组成的矩阵 mat ，请输出一个大小相同的矩阵，其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。
 *  两个相邻元素间的距离为 1 。
 *  https://leetcode.cn/problems/01-matrix/solutions/203486/2chong-bfs-xiang-jie-dp-bi-xu-miao-dong-by-sweetie/
 * 输入：mat = [[0,0,0],[0,1,0],[0,0,0]]
 * 输出：[[0,0,0],[0,1,0],[0,0,0]]
 * @author: chaidl  ！
 * @create: 2022-03-21 14:22
 */
public class 矩阵 {
    public int[][] updateMatrix(int[][] mat) {
        // 首先将所有的 0 都入队，并且将 1 的位置设置成 -1，表示该位置是 未被访问过的 1
        Queue<int[]> queue = new LinkedList<int[]>();
        int m = mat.length, n = mat[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (mat[i][j]==0){
                    queue.offer(new int[] {i,j});
                }else {
                    mat[i][j]=-1;
                }
            }
        }
    //    定义两个dx和dy用来查询上下左右相邻元素
        int[] dx=new int[]{-1,1,0,0};
        int[] dy=new int[]{0,0,-1,1};
    //    从队列中依次弹出元素
        while (!queue.isEmpty()){
            int[] point = queue.poll();
            //去除这个元素的x,y坐标位置
            int x=point[0], y=point[1];
            for (int i = 0; i < 4; i++) {
            //    取出上下左右的值，并且+x，y,就是为了得到他的上下左右值得坐标
                int newX=x+dx[i];
                int newY=y+dy[i];
                // 如果四邻域的点是 -1，表示这个点是未被访问过的 1
                // 所以这个点到 0 的距离就可以更新成 matrix[x][y] + 1。
                if (newX>=0 && newX < m && newY>=0 && newY<n && mat[newX][newY] == -1){
                    mat[newX][newY]=mat[x][y]+1;
                    queue.offer(new int[]{newX , newY});
                }
            }

        }
        return mat;
    }
}
